/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Administrator
 */
import java.util.*;

public class Heap<E extends Comparable<E>> implements Comparator<E>,PriorityQueueInterface<E>{

    protected Vector<E> data;

    public Heap(){
        data = new Vector<E>();
    }

    public Heap(Vector<E> v){
        int n;
        data = new Vector<E>(v.size());
        for(int i = 0; i < v.size(); i++)
            add(v.get(i));
    }

    public void add(E value){
        data.add(value);
        percolateUp(data.size() - 1);
    }

    public E getFirst(){
        return data.get(0);
    }

    public E remove(){
        E minVal = data.get(0);
        data.set(0, data.get(data.size() - 1));
        data.setSize(data.size() - 1);
        if (data.size() > 1)
            pushDownRoot(0);
        return minVal;
    }

    protected static int parent(int i){
        return (i-1)/2;
    }

    protected static int left(int i){
        return 2*i+1;
    }

    protected static int right(int i){
        return 2*(i+1);
    }

    protected void percolateUp(int index){
        int parent = parent(index);
        E value = data.get(index);
        while ((index > 0) && compare(value,(data.get(parent))) < 0){
            data.set(index, data.get(parent));
            index = parent;
            parent = parent(index);
        }
        data.set(index, value);
    }

    protected void pushDownRoot(int root){
        int heapsize = data.size();
        E value = data.get(root);
        while (root < heapsize){
            int sonpos = left(root);
            if (sonpos < heapsize){
                if((right(root) < heapsize) && (compare(data.get(sonpos+1),(data.get(sonpos))) < 0))
                    sonpos++;
                if(compare(data.get(sonpos),(value)) < 0){
                    data.set(root, data.get(sonpos));
                    root = sonpos;
                }
                else{
                    data.set(root, value);
                    return;
                }
            }
            else{
                data.set(root, value);
                return;
            }
        }
    }
    
    public int compare(E x, E y){
        if (x.compareTo(y) < 0)
            return(1);
        if (x.compareTo(y) > 0)
            return(-1);
        return(0);
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }
}
